The CAP theorem is a fundamental result that applies to distributed storagesystems. In this paper, we first present and prove two CAP-like impossibilitytheorems. To state these theorems, we present probabilistic models tocharacterize the three important elements of the CAP theorem: consistency (C),availability or latency (A), and partition tolerance (P). The theorems show theun-achievable envelope, i.e., which combinations of the parameters of the threemodels make them impossible to achieve together. Next, we present the design ofa class of systems called PCAP that perform close to the envelope described byour theorems. In addition, these systems allow applications running on a singledata-center to specify either a latency SLA or a consistency SLA. The PCAPsystems automatically adapt, in real-time and under changing networkconditions, to meet the SLA while optimizing the other C/A metric. Weincorporate PCAP into two popular key-value stores -- Apache Cassandra andRiak. Our experiments with these two deployments, under realistic workloads,reveal that the PCAP system satisfactorily meets SLAs, and performs close tothe achievable envelope. We also extend PCAP from a single data-center tomultiple geo-distributed data-centers.
展开▼
